/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

Node::Node(PageId new_pid)
{
	pid = new_pid;
}

linked_Nodes::linked_Nodes()
{
	head = 0;
	tail = 0;
	count = 0;
}

void linked_Nodes::free_List()
{
	Node* temp;
	
	while(tail != head)
	{
		temp = tail->prev;
		delete tail;
		tail = temp;
	}
	
	delete head;
}

void linked_Nodes::endValue(PageId& page_Id)
{
	page_Id = tail->pid;
	Node* temp;
	
	if(tail->prev) 
	{
		temp = tail->prev;
	}
	else
	{
		return;
	}
	delete tail;
	tail = temp;
}

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{	
	treeHeight = 0;
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	//cout<< "rootpid: " << rootPid << "		height: " << treeHeight << "/n";

	RC rc = pf.open(indexname, mode);
	if(rc != 0)
	{
		return RC_FILE_OPEN_FAILED;
	}
	
	current_Mode = mode;
	if(mode == 'w')
	{
		return 0;
	}
	
	char buf[PageFile::PAGE_SIZE];
	rc = pf.read(0, buf);
	if(rc != 0)
	{
		return RC_FILE_READ_FAILED;
	}
	
	char* iterate_Buf = &(buf[0]);
	// get rootPid value
	memcpy(&rootPid, iterate_Buf, sizeof(PageId));
	iterate_Buf += sizeof(PageId);
	// get treeHeight value
	memcpy(&treeHeight, iterate_Buf, sizeof(int));
	
    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{	
	RC rc;
	char buf[PageFile::PAGE_SIZE];
	char* iterate_Buf = &(buf[0]);
	
	if(current_Mode == 'w')
	{
		memset(iterate_Buf, 0, PageFile::PAGE_SIZE);
		memcpy(iterate_Buf, &rootPid, sizeof(PageId));
		iterate_Buf += sizeof(PageId);
		memcpy(iterate_Buf, &treeHeight, sizeof(PageId));
		
		rc = pf.write(0, buf);
		if(rc != 0)
		{
			return RC_FILE_WRITE_FAILED;
		}
	}
	
	rc = pf.close();
	return rc;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	// make cursor point to the first index entry
	IndexCursor cursor;
	locate(key, cursor);
	
	BTLeafNode leaf_Node;
	RC rc;
	if(treeHeight == 1)
	{
		rc = leaf_Node.read(cursor.pid, pf);
		if(rc != 0)
		{
			return RC_FILE_READ_FAILED;
		}
		
		rc = leaf_Node.insert(key, rid);
		if(rc != 0)
		{
			goto split_And_Insert;
		}
		
		rc = leaf_Node.write(cursor.pid, pf);
		if(rc != 0)
		{
			return RC_FILE_WRITE_FAILED;
		}
		return 0;
	}
	
	rc = leaf_Node.read(cursor.pid, pf);
	if(rc != 0)
	{
		return RC_FILE_READ_FAILED;
	}
	
	rc = leaf_Node.insert(key, rid);
	if(rc != 0)
	{
		split_And_Insert:
		
		int sibling_Key;
		BTLeafNode sibling_Node;
		
		leaf_Node.insertAndSplit(key, rid, sibling_Node, sibling_Key);
		
		PageId next_Node = leaf_Node.getNextNodePtr();
		sibling_Node.setNextNodePtr(next_Node);
		leaf_Node.setNextNodePtr(pf.endPid());
		
		rc = leaf_Node.write(cursor.pid, pf);
		if(rc != 0)
		{
			return RC_FILE_WRITE_FAILED;
		}
		
		rc = sibling_Node.write(pf.endPid(), pf);
		if(rc != 0)
		{
			return RC_FILE_WRITE_FAILED;
		}
		
		if(treeHeight == 1)
		{
			BTNonLeafNode root_Node;
			root_Node.initializeRoot(cursor.pid, sibling_Key, pf.endPid()-1);
			
			rc = root_Node.write(pf.endPid(), pf);
			if(rc != 0);
			{
				return RC_FILE_WRITE_FAILED;
			}
			
			rootPid = pf.endPid() - 1;
			treeHeight++;
			return 0;
		}
		
		PageId old_Pid;
		PageId page_Id;
		int i = 0;
		int id_Key;
		BTNonLeafNode sibling;
		BTNonLeafNode node;
		
		do
		{
			linked_List.endValue(page_Id);
			
			rc = node.read(page_Id, pf);
			if(rc != 0)
			{
				return RC_FILE_READ_FAILED;
			}
			
			if(i == 0)
			{
				rc = node.insert(sibling_Key, pf.endPid() - 1);
				
				if(rc == 0)
				{
					rc = node.write(page_Id, pf);
					if(rc != 0)
					{
						return RC_FILE_WRITE_FAILED;
					}
					break;
				}
				else
				{
					node.insertAndSplit(sibling_Key, cursor.pid, sibling, id_Key);
					sibling.write(pf.endPid(), pf);;
					
					rc = node.write(page_Id, pf);
					if(rc != 0)
					{
						return RC_FILE_WRITE_FAILED;
					}
				}
			}
			else
			{
				rc = node.insert(id_Key, old_Pid);
				if(rc !=0)
				{
					rc = node.write(page_Id, pf);
					if(rc !=0)
					{
						return RC_FILE_WRITE_FAILED;
					}
					break;
				}
				else
				{
					node.insertAndSplit(id_Key, old_Pid, sibling, id_Key);
					rc = sibling.write(pf.endPid(), pf);
					if(rc != 0)
					{
						return RC_FILE_WRITE_FAILED;
					}
					
					if(page_Id == rootPid)
					{
						BTNonLeafNode root;
						root.initializeRoot(page_Id, id_Key, pf.endPid() - 1);
						
						rc = root.write(pf.endPid(), pf);
						if(rc != 0)
						{
							return RC_FILE_WRITE_FAILED;
						}
						treeHeight++;
						rootPid = pf.endPid() - 1;
					}
					rc = node.write(page_Id, pf);
					if(rc != 0)
					{
						return RC_FILE_WRITE_FAILED;
					}
					break;
				}
			}
			i = 1;
		}while(page_Id != rootPid);
	}
	
	rc = leaf_Node.write(cursor.pid, pf);
	if(rc != 0)
	{
		return RC_FILE_WRITE_FAILED;	
	}
	
	linked_List.free_List();
	
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	RC rc;
	if(treeHeight == 0)
	{
		cursor.eid = 0;
		cursor.pid = 1;
		rootPid = 1;
		treeHeight++;
	}
	else if(treeHeight == 1)
	{
		BTLeafNode root_Node;
		int eid;
		
		rc = root_Node.read(rootPid, pf);
		if(rc != 0)
		{
			return RC_FILE_READ_FAILED;
		}
		
		rc = root_Node.locate(searchKey, eid);
		if(rc != 0)
		{
			return RC_NO_SUCH_RECORD;
		}
		
		cursor.eid = eid;
		cursor.pid = rootPid;
	}
	else
	{
		BTNonLeafNode node;
		
		rc = node.read(rootPid, pf);
		if(rc != 0)
		{
			return RC_FILE_READ_FAILED;
		}
		
		int count = 1;
		while(count < treeHeight)
		{
			if(count == 1)
			{
				if(linked_List.count == 0)
				{
					linked_List.head = new Node(rootPid);
					linked_List.tail = linked_List.head;
					linked_List.tail->next = 0;
					linked_List.head->prev = 0;
					linked_List.count == 1;
				}
				else
				{
					Node* temp = new Node(rootPid);
					linked_List.tail->next = temp;
					temp->next = 0;
					temp->prev = linked_List.tail;
					linked_List.tail = temp;
					linked_List.count++;
				}
			}
			else
			{
				if(linked_List.count == 0)
				{
					linked_List.head = new Node(next_Pid);
					linked_List.tail = linked_List.head;
					linked_List.tail->next = 0;
					linked_List.head->prev = 0;
					linked_List.count == 1;
				}
				else
				{
					Node* temp = new Node(next_Pid);
					linked_List.tail->next = temp;
					temp->next = 0;
					temp->prev = linked_List.tail;
					linked_List.tail = temp;
					linked_List.count++;
				}
			}
			
			rc = node.locateChildPtr(searchKey, next_Pid);
			if(rc != 0)
			{
				return RC_NO_SUCH_RECORD;
			}
			
			rc = node.read(next_Pid, pf);
			if(rc != 0)
			{
				return RC_FILE_READ_FAILED;
			}
			
			count++;
		}
		
		cursor.eid = 0;
		cursor.pid = next_Pid;
	}
	
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode node;
	RC rc = node.read(cursor.pid, pf);
	
	if(rc != 0)
	{
		return RC_FILE_READ_FAILED;
	}
	
	rc = node.readEntry(cursor.eid, key, rid);
	
	if(rc != 0)
	{
		return RC_INVALID_RID;
	}
	
	if (cursor.eid < node.getKeyCount() - 1)
	{
		cursor.eid++;
	}
	else
	{
		cursor.eid = 0;
		int i = node.getNextNodePtr();
		
		if(i == 0)
		{
			return RC_END_OF_TREE;
		}
		
		cursor.pid = i;
	}
	
    return 0;
}
